#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    int superEggDrop(int k, int n) {
        const static int N = 1e4 + 10;
        const static int K = 110;
        int dp[K][N] = { 0 };
        for (int i = 1; i <= k; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (j >= i)
                {
                    int left = 1, right = j / 2;
                    int min1 = INT_MAX;
                    while (right >= left)
                    {
                        int mid = (right - left) / 2 + left;
                        int num1 = dp[i - 1][mid - 1];
                        int num2 = dp[i][j - mid];
                        if (num1 > num2) right = mid - 1;
                        else if (num1 < num2) left = mid + 1;
                        else
                        {
                            min1 = num1;
                            break;
                        }
                    }
                    if (right < left) min1 = max(dp[i - 1][left - 1], dp[i][j - left]);

                    if (dp[i][j] == 0) dp[i][j] = INT_MAX / 2;
                    if (i == 1) dp[i][j] = j;
                    else dp[i][j] = min(dp[i][j], min1 + 1);
                }
                else
                {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        // for(int i = 1; i <= k; i++)
        // {
        //     for(int j = 1; j <= n; j++)
        //     {
        //         cout << dp[i][j] << ' ';
        //     }
        //     cout << endl;
        // }
        return dp[k][n];
    }
};